class Solution:
	# @return an integer
	def minDistance(self, word1, word2):
		row, col = len(word1), len(word2)
		if row == 0 or col == 0:
			return max(row, col)
		dp = [[0 for i in xrange(col+1)] for x in xrange(row+1)]
		for j in xrange(col+1):
			dp[0][j] = j
		for i in xrange(row+1):
			dp[i][0] = i
		for i in xrange(1, row+1):
			for j in xrange(1, col+1):
				ad = 0 if word1[i-1] == word2[j-1] else 1
				dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1] + ad)
		return dp[row][col]

if __name__ == '__main__':
	a = "sot"
	b = "stop"
	so = Solution()
	print(so.minDistance(a,b))